package algorithm;

/**
 * leetcode
 *
 * @author apple
 * 大顶堆 小顶堆 测试
 **/
public class UtilHeap {

    /**
     * 堆数组 从下标1开始存数据 测试
     **/
    int[] heapList;

    /**
     * 堆容量
     **/
    private int capacity;
    /**
     * 堆里实际存的元素数量
     **/
    private int count;

    public UtilHeap(int capacity) {
        this.capacity = capacity;
        /** 创建新数组。因为堆的数组是从1开始存储数据，所以，这里数组的容量要加1**/
        heapList = new int[this.capacity + 1];
        /**初始数量为0**/
        this.count = 0;
    }

    // 插入大顶堆

    /**
     * @param
     * @param value:要插入的值
     * @param k:备用
     */
    public boolean insertMaxHeap(UtilHeap heap, int value, int k) {
        int count = heap.count;
        if (count >= k) {
            return false;
        }
        int[] list = heap.heapList;

        // 堆中元素为0个，直接将插入的值放在数组第1个位置，不是第0个
        if (count == 0) {
            list[1] = value;
            count++;
        } else {
            // 堆中有元素，即将新增元素放在最后一个元素的后面，索引加1
            // 然后排序，将新增元素放在合适的位置上。即调整堆。
            list[count + 1] = value;
            count++;
            int i = count;
            /** 自下而上堆化**/
            while (i / 2 > 0 && list[i] >= list[i / 2]) {
                int temp = list[i];
                list[i] = list[i / 2];
                list[i / 2] = temp;
                i = i / 2;
            }
        }
        heap.count = count;
        return true;
    }

    // 小顶堆插入元素

    /**
     * @param heap  堆
     * @param value 插入的值
     * @param k     堆的总容量
     */
    public boolean insertMinHeap(UtilHeap heap, int value, int k) {
        int count = heap.count;
        if (count >= k) {
            return false;
        }
        int[] list = heap.heapList;

        // 堆中元素为0个，直接将插入的值放在数组第1个位置，不是第0个
        if (count == 0) {
            list[1] = value;
            count++;
        } else {
            // 堆中有元素，即将新增元素放在最后一个元素的后面，索引加1
            // 然后排序，将新增元素放在合适的位置上。即调整堆。
            list[count + 1] = value;
            count++;
            int i = count;
            while (i / 2 > 0 && list[i] <= list[i / 2]) {
                /** 自下而上堆化**/
                int temp = list[i];
                list[i] = list[i / 2];
                list[i / 2] = temp;
                i = i / 2;
            }
        }
        heap.count = count;
        return true;
    }

    public void printHeapList(int[] list, int count) {
        for (int i = 1; i <= count; i++) {
            System.out.println(i + "-->" + list[i]);
        }
        System.out.println("----------");

    }

    // 删除大顶堆堆顶的元素

    /**
     * 将堆顶元素和堆的最后一个元素兑换位置，然后删除最后一个元素(此时为堆顶元素)，再堆化
     *
     * @param heap
     */
    public void removeTopOfMaxHeap(UtilHeap heap) {
        int[] heapList = heap.heapList;
        int count = heap.count;
        // 兑换堆顶元素和最后一个元素
        heapList[1] = heapList[count];
        count--;
        heap.count = count;
        heapifyMaxHeap(heapList, count, 1);
        buildMaxHeap(heapList, count);
    }

    // 构建大顶堆
    public void buildMaxHeap(int[] heapList, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapifyMaxHeap(heapList, n, i);
        }
    }

    /**
     * 大顶堆 堆化
     *
     * @param heapList
     * @param n        堆的元素数量
     * @param i        结束指针
     */
    public void heapifyMaxHeap(int[] heapList, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && heapList[i] < heapList[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= n && heapList[maxPos] < heapList[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i) {
                break;
            }
            int temp = heapList[i];
            heapList[i] = heapList[maxPos];
            heapList[maxPos] = temp;
        }

    }

    // 删除小顶堆堆顶的元素
    public void removeTopOfMinHeap(UtilHeap heap) {
        int[] heapList = heap.heapList;
        int count = heap.count;
        // 兑换堆顶元素和最后一个元素
        heapList[1] = heapList[count];
        count--;
        heap.count = count;
        heapifyMinHeap(heapList, count, 1);
        // 构建小顶堆
        buildMinHeap(heapList, count);
    }

    /**
     * 小顶堆 堆化
     *
     * @param heapList
     * @param n        堆的元素数量
     * @param i        结束指针
     */
    public void heapifyMinHeap(int[] heapList, int n, int i) {
        while (true) {
            int minPos = i;
            if (i * 2 <= n && heapList[i] > heapList[i * 2]) {
                minPos = i * 2;
            }
            if (i * 2 + 1 <= n && heapList[minPos] > heapList[i * 2 + 1]) {
                minPos = i * 2 + 1;
            }
            if (minPos == i) {
                break;
            }
            int temp = heapList[i];
            heapList[i] = heapList[minPos];
            heapList[minPos] = temp;
        }

    }

    /**
     * 排序小顶堆
     **/
    public void buildMinHeap(int[] heapList, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapifyMinHeap(heapList, n, i);
        }
    }

    // 获取堆顶元素
    public int getTopOfHeap(int[] heapList) {
        return heapList[1];
    }

    // 获取堆中元素的数量
    public int getCountOfHeap(UtilHeap utilHeap) {
        return utilHeap.count;
    }

    // 取最大的k个数，使用小顶堆
    public int[] getMaxTopK(int[] heapList, int value) {
        System.out.println(value);
        if (value > heapList[1]) {
            // 如果新数据大于堆顶数，则将堆顶元素删除，新元素加入，即将原堆顶元素置换成新元素，然后堆化
            heapList[1] = value;
            buildMinHeap(heapList, heapList.length - 1);
        }
        System.out.println("-->" + getTopOfHeap(heapList));

        return heapList;
    }

    // 取最小的k个数，使用大顶堆
    public int[] getMinTopK(int[] heapList, int value) {
        System.out.println(value);
        if (value < heapList[1]) {
            // 如果新数据小于堆顶数，则将堆顶元素删除，新元素加入，即将原堆顶元素置换成新元素，然后堆化
            heapList[1] = value;
            buildMaxHeap(heapList, heapList.length - 1);
        }
        System.out.println("-->" + getTopOfHeap(heapList));
        return heapList;
    }

    public static void main(String[] args) {
        /*
         * System.out.println("大顶堆");
         * UtilHeap maxHeap = new UtilHeap(10);
         * maxHeap.insertMaxHeap(maxHeap, 1, 10); maxHeap.insertMaxHeap(maxHeap, 2, 10);
         * maxHeap.insertMaxHeap(maxHeap, 4, 10); maxHeap.insertMaxHeap(maxHeap, 6, 10);
         * maxHeap.insertMaxHeap(maxHeap, 8, 10); maxHeap.insertMaxHeap(maxHeap, 7, 10);
         * maxHeap.insertMaxHeap(maxHeap, 12, 10); maxHeap.insertMaxHeap(maxHeap, 9,
         * 10);
         *
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         *
         * maxHeap.removeTopOfMaxHeap(maxHeap);
         * System.out.println("top of heap="+maxHeap.getTopOfHeap(maxHeap.heapList));
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         *
         * maxHeap.removeTopOfMaxHeap(maxHeap);
         * System.out.println("top of heap="+maxHeap.getTopOfHeap(maxHeap.heapList));
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         *
         * maxHeap.removeTopOfMaxHeap(maxHeap);
         * System.out.println("top of heap="+maxHeap.getTopOfHeap(maxHeap.heapList));
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         *
         * maxHeap.removeTopOfMaxHeap(maxHeap);
         * System.out.println("top of heap="+maxHeap.getTopOfHeap(maxHeap.heapList));
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         *
         * maxHeap.removeTopOfMaxHeap(maxHeap);
         * System.out.println("top of heap="+maxHeap.getTopOfHeap(maxHeap.heapList));
         * maxHeap.printHeapList(maxHeap.heapList, maxHeap.count);
         */

        System.out.println("大顶堆的最小4个数");
        int k = 4;
        UtilHeap maxHeap_2 = new UtilHeap(4);
        maxHeap_2.insertMaxHeap(maxHeap_2, 1, k);
        maxHeap_2.insertMaxHeap(maxHeap_2, 20, k);
        maxHeap_2.insertMaxHeap(maxHeap_2, 49, k);
        maxHeap_2.insertMaxHeap(maxHeap_2, 69, k);
        maxHeap_2.printHeapList(maxHeap_2.heapList, maxHeap_2.count);
        maxHeap_2.getMinTopK(maxHeap_2.heapList, 20);
        maxHeap_2.printHeapList(maxHeap_2.heapList, maxHeap_2.count);
        maxHeap_2.getMinTopK(maxHeap_2.heapList, 14);
        maxHeap_2.printHeapList(maxHeap_2.heapList, maxHeap_2.count);
        maxHeap_2.getMinTopK(maxHeap_2.heapList, 17);
        maxHeap_2.printHeapList(maxHeap_2.heapList, maxHeap_2.count);

        /*
         * System.out.println("小顶堆"); UtilHeap minHeap = new UtilHeap(16);
         * minHeap.insertMinHeap(minHeap, 9, 10); minHeap.insertMinHeap(minHeap, 6, 10);
         * minHeap.insertMinHeap(minHeap, 1, 10); minHeap.insertMinHeap(minHeap, 7, 10);
         * minHeap.insertMinHeap(minHeap, 3, 10); minHeap.insertMinHeap(minHeap, 5, 10);
         * minHeap.insertMinHeap(minHeap, 12, 10); minHeap.insertMinHeap(minHeap, 11,
         * 10);
         *
         * minHeap.printHeapList(minHeap.heapList, minHeap.count);
         *
         *
         * minHeap.removeTopOfMinHeap(minHeap); minHeap.printHeapList(minHeap.heapList,
         * minHeap.count);
         *
         *
         * minHeap.removeTopOfMinHeap(minHeap); minHeap.printHeapList(minHeap.heapList,
         * minHeap.count);
         *
         * minHeap.removeTopOfMinHeap(minHeap); minHeap.printHeapList(minHeap.heapList,
         * minHeap.count);
         *
         *
         * minHeap.removeTopOfMinHeap(minHeap); minHeap.printHeapList(minHeap.heapList,
         * minHeap.count);
         *
         * minHeap.removeTopOfMinHeap(minHeap); minHeap.printHeapList(minHeap.heapList,
         * minHeap.count);
         */

        /*
         * System.out.println("取最大的三个数，使用小顶堆"); UtilHeap minHeap_2 = new UtilHeap(3);
         * minHeap_2.insertMinHeap(minHeap_2, 9, 3); minHeap_2.insertMinHeap(minHeap_2,
         * 6, 3); minHeap_2.insertMinHeap(minHeap_2, 1, 3);
         * minHeap_2.printHeapList(minHeap_2.heapList, minHeap_2.count);
         *
         * minHeap_2.getMaxTopK(minHeap_2.heapList, 4);
         * minHeap_2.printHeapList(minHeap_2.heapList, minHeap_2.count);
         *
         * minHeap_2.getMaxTopK(minHeap_2.heapList, 6);
         * minHeap_2.printHeapList(minHeap_2.heapList, minHeap_2.count);
         * minHeap_2.getMaxTopK(minHeap_2.heapList,8);
         * minHeap_2.printHeapList(minHeap_2.heapList, minHeap_2.count);
         * minHeap_2.getMaxTopK(minHeap_2.heapList,7);
         * minHeap_2.printHeapList(minHeap_2.heapList, minHeap_2.count);
         */
    }
}
